package com.sicheng.algorithm.node;

import lombok.Data;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/9/25 13:27
 */
@Data
@SuppressWarnings("unused")
public class RandomListNode {


    private ListNode head;

    public static void main(String[] args) {
        ListNode head = ListNode.initList(new int[]{1, 2, 3, 4, 5});
        ListNode tail = ListNode.getTail(head);
        tail.random = head;
        head.next.next.random = tail;
        head.random = head.next;

        System.out.println("==================");

        ListNode copyListNode = copyListNode(head);
        ListNode.list(copyListNode);

    }

    /**
     * 输入一个复杂链表
     * （每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
     * 返回结果为复制后复杂链表的 head。
     */
    public static ListNode copyListNode(ListNode head) {

        if (head == null)
            return null;

        ListNode temp = head;
        //1. 将原list的每个节点复制出来挂在next域上,   N->N'
        while (temp.next != null) {
            ListNode temp_next = temp.next;
            ListNode node = new ListNode(temp.val);
            node.next = temp_next;
            temp.next = node;
            temp = temp_next;
        }

        temp.next = new ListNode(temp.val);

        //2. 给N'设置random域,
        //   当N.random!=null ======>  N'.random=N.random.next
        temp = head;
        ListNode temp_next = temp.next.next;

        while (temp_next != null) {
            if (temp.random != null) {
                temp.next.random = temp.random.next;
            }
            temp = temp_next;
            temp_next = temp_next.next.next;

        }

        if (temp.random != null) {
            temp.next.random = temp.random.next;
        }


        //3. 拆分最后的list，奇数节点是原list，偶数节点是copy的

        temp = head;
        head = head.next;

        ListNode temp_cp = head;
        while (temp_cp.next != null) {
            temp.next = temp_cp.next;
            temp = temp_cp.next;
            temp_cp.next = temp.next;
            temp_cp = temp.next;
        }

        temp.next = null;
        return head;
    }
}
